import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int result = 0;
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }

        if (k > 0 && k % 2 != 0) {
            Arrays.sort(nums);
            nums[0] *= -1;
        }

        for (int num : nums) {
            result += num;
        }

        return result;
    }
}
